package org.lyc.dp;

/**
 * 统计全为1的正方形子矩阵
 * https://leetcode.cn/problems/count-square-submatrices-with-all-ones/
 *
 * @author Liu Yicong
 * @date 2024/3/4
 */
public class LCountSquares {

	/**
	 * [0,1,1,1],
	 * [1,1,1,1],
	 * [0,1,1,1]
	 * 边长为1的10个, 边长为2的4个, 边长为3的1个, 总计15个
	 */
	static int[][] matrix1 = {{0, 1, 1, 1}, {1, 1, 1, 1}, {0, 1, 1, 1}};

	/**
	 * [1,0,1],
	 * [1,1,0],
	 * [1,1,0]
	 * 边长为1的6个, 边长为2的1个, 总计7个
	 */
	static int[][] matrix2 = {{1, 0, 1}, {1, 1, 0}, {1, 1, 0}};

	public static void main(String[] args) {
		System.out.println(countSquares(matrix1));
		System.out.println(countSquares(matrix2));
	}

	/**
	 * 方法2
	 * 这个函数使用一个二维数组 dp 来记录每个位置为右下角的正方形子矩阵的边长。
	 * 对于每个矩阵元素，如果它为 1，那么可以构成一个正方形子矩阵，通过比较上方、左方和左上方的元素，
	 * 确定以当前元素为右下角的正方形子矩阵的边长。将每个正方形子矩阵的边长累加到 sum 中，
	 * 最后返回 sum，即所有正方形子矩阵的数量。
	 * 对于以下矩阵来说
	 * [0, 1, 1, 1]
	 * [1, 1, 1, 1]
	 * [0, 1, 1, 1]
	 * 其对应的dp矩阵的最终值为
	 * [0, 0, 0, 0, 0]
	 * [0, 0, 1, 1, 1]
	 * [0, 1, 1, 2, 2]
	 * [0, 0, 1, 2, 3]
	 *
	 * @param matrix
	 * @return
	 */
	public static int countSquares(int[][] matrix) {
		int m = matrix.length;
		int n = matrix[0].length;
		int[][] dp = new int[m + 1][n + 1];
		int sum = 0;
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				if (matrix[i - 1][j - 1] == 1) {
					dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;
					sum += dp[i][j];
				}
			}
		}
		return sum;
	}

	/**
	 * 方法1
	 *
	 * @param matrix
	 * @return
	 */

	public static int countSquares1(int[][] matrix) {
		//n表示矩阵的列数, m表示矩阵的行数, total表示矩阵拥有的元素总数, maxLen表示子矩阵的最大边长
		int n = matrix.length;
		int m = matrix[0].length;
		int maxLen = Math.min(n, m);
		//
		boolean[][][] dp = new boolean[maxLen + 1][n][m];
		int result = 0;
		for (int l = 1; l <= maxLen; l++) {
			for (int i = 0; i + l <= n; i++) {
				for (int j = 0; j + l <= m; j++) {
					if (l == 1) {
						dp[l][i][j] = matrix[i][j] == 1;
					} else {
						dp[l][i][j] = matrix[i][j] == 1
								&& dp[l - 1][i][j + 1] && dp[l - 1][i + 1][j] && dp[l - 1][i + 1][j + 1];
					}
					result += dp[l][i][j] ? 1 : 0;
				}
			}
		}
		return result;
	}
}
